#include <iostream>
#include <assert.h>

namespace Y190615_exam_02_3_4_Reversing_Linked_List {
int main();

typedef int ElementType;

typedef struct DataNode* PDataNode;
struct DataNode {
	ElementType address;
	ElementType data;
	ElementType next;
};

typedef struct LNode* List;
typedef List LNodeArray;
typedef List LPosition;
struct LNode {
	PDataNode value;
	List next;
};

typedef struct SNode* Stack;
struct SNode {
	List data;
	Stack next;
};

PDataNode createDataNode(ElementType address, ElementType data, ElementType next)
{
	PDataNode node = (PDataNode)malloc(sizeof(struct DataNode));
	node->address = address;
	node->data = data;
	node->next = next;
	return node;
}

List createLNode(PDataNode data) {
	List node = (List)malloc(sizeof(struct LNode));
	node->value = data;
	node->next = NULL;
	return node;
}

Stack createSNode(LPosition data) {
	Stack node = (Stack)malloc(sizeof(struct SNode));
	node->data = data;
	node->next = NULL;
	return node;
}

Stack stack_push(Stack s, LPosition p)
{
	Stack node = createSNode(p);
	node->next = s->next;
	s->next = node;
	return s;
}

LPosition stack_pop(Stack s)
{
	Stack ps = s->next;
	LPosition p = ps->data;
	s->next = ps->next;
	free(ps);
	return p;
}

void stack_free(Stack s) {
	Stack p;
	while (s) {
		p = s->next;
		free(s);
		s = p;
	}
}

List read_input(int N) {
	int address, data, next;
	assert(N > 0);
	LNodeArray values = (List)malloc(N * sizeof(struct LNode));
	LPosition p = values;
	int i = N;
	while (i--) {
		std::cin >> address >> data >> next;
		p->value = createDataNode(address, data, next);
		p->next = NULL;
		++p;
	}
	return values;
}

LPosition find_data(LNodeArray datas, ElementType address, int N) {
	LPosition p = datas;
	for (int i = 0; i < N; ++i) {
		if (p->value->address == address)
			return p;
		++p;
	}
	return NULL;
}

List build_list(LNodeArray datas, ElementType address, int* nn) {
	List L = createLNode(NULL);
	List p = L;
	int n = 0;
	while (address != -1)
	{
		LPosition data = find_data(datas, address, *nn);
		p->next = data;
		p = data;
		address = data->value->next;
		++n;
	}
	*nn = n;
	return L->next;
}

void print_list(List L)
{
	while (L && L->next) {
		printf("%05d %d %05d\n", L->value->address, L->value->data, L->next->value->address);
		L = L->next;
	}
	printf("%05d %d -1\n", L->value->address, L->value->data);
}

List KN_reverse(List L, int K, int N) {
	List head = createLNode(NULL);
	List head0 = head;
	head->next = L;
	List new_node = L;
	List tmp;
	List old_node = new_node->next;
	for (int i = 0; i <= N - K; i+=K) {
		int count = 1;
		while (count < K) {
			tmp = old_node->next;
			old_node->next = new_node;
			new_node = old_node;
			old_node = tmp;
			count++;
		}
		tmp = head->next;
		head->next->next = old_node;
		head->next = new_node;
		head = tmp;
		new_node = old_node;
		old_node = new_node->next;
	}
	return head0->next;
}

int main()
{
	int first, N, K;
	List sl;
	std::cin >> first >> N >> K;
	LNodeArray datas = read_input(N);
	int nn = N;
	List nl = build_list(datas, first, &nn);
	if (nn < 1){
		printf("0 0\n");
	}
	else if (K <= 1 || K > nn){
		print_list(nl);
	}
	else {
		sl = KN_reverse(nl, K, nn);
		print_list(sl);
	}

	return 0;
}
}

int main_Y190615_exam_02_3_4_Reversing_Linked_List()
{
	return Y190615_exam_02_3_4_Reversing_Linked_List::main();
}